//package personal.abandoned;
//
//import personal.scanner.ScannerFiniteAutomata;
//
//import java.util.ArrayList;
//import java.util.List;
//import java.util.Set;
//
///**
// * 正则表达式转 NFA，我们禁止正则表达式中出现*|()
// *
// * @author 陈渤林
// */
//public class StREToNFAConverter {
////	/** 临时测试程序 */
////	public static void main(String[] args) {
////		Set<Integer> transitions = new HashSet<Integer>();
////		for (int i = 1; i < 128; ++i)
////			transitions.add(i);
////		String re = "a|b";
////		FiniteAutomata ans = new StREToNFAConverter().convert(re, transitions, 7);
////		try (FileOutputStream fout = new FileOutputStream("./data/output.md")) {
////			fout.write(ans.toMermaid().getBytes()); // 文件输出
////		} catch (Exception e) {
////		}
//////		System.out.println(ans);
////	}
//
//    /**
//     * 要转换的正则表达式
//     */
//    private StandardRE re = null;
//    /**
//     * 正则表达式的字母表
//     */
//    private Set<Integer> transitions = null;
//    /**
//     * 返回的 nfa
//     */
//    private ScannerFiniteAutomata nfa = new ScannerFiniteAutomata();
//
//    /**
//     * 找出与指定的左括号匹配的右括号
//     *
//     * @param left_pos 指定的左括号的下标
//     * @return 匹配的右括号的下标
//     */
//    private int findMatchedRightIndex(int left_pos) throws IllegalArgumentException {
//        if (this.re.get(left_pos) != StandardRE.LEFT_BRACKET)
//            throw new IllegalArgumentException("传入参数处不是左括号");
//        int left_cnt = 1; // 左括号数量计数
//        for (int i = left_pos + 1; i < this.re.size(); ++i) {
//            if (this.re.get(i) == StandardRE.LEFT_BRACKET) ++left_cnt;
//            if (this.re.get(i) == StandardRE.RIGHT_BRACKET) --left_cnt;
//            if (left_cnt == 0) return i; // 匹配成功
//        }
//        return -1;
//    }
//
//    /**
//     * 将 re[l, r] 沿 | 分割。注意，我们将 () 子区间视为一个整体，其不会被划分开
//     *
//     * @param l 指定区间左端点
//     * @param r 指定区间右端点
//     * @return 分割后的区间，以 list 返回，list 中每两个元素视为一个二元组
//     */
//    private List<Integer> divideByUnion(int l, int r) {
//        List<Integer> ret = new ArrayList<Integer>();
//        ret.add(l);
//        for (int i = l; i <= r; ++i) { // 遍历
//            if (this.re.get(i) == StandardRE.LEFT_BRACKET) { // 跳过 () 子区间
//                i = this.findMatchedRightIndex(i);
//                continue;
//            }
//            if (this.re.get(i) == StandardRE.UNION) {
//                ret.add(i - 1);
//                ret.add(i + 1);
//            }
//        }
//        ret.add(r);
//        return ret;
//    }
//
//    /**
//     * 处理 re[l, r] 中的 | 运算，子图节点编号范围是 [s, t]。按指定区间逐个递归处理，再将处理结果合并，
//     *
//     * @param s         初始编号，
//     * @param intervals 给出的指定区间，每两个元素视为一个二元组
//     * @return 结束编号 t，
//     */
//    private int convertByUnion(int s, final List<Integer> intervals) {
//        int usedId = s; // 当前编号 usedId，即已使用的最大编号，我们使用 ++usedId 进行分配
//        // 记录所有被 | 运算隔开的区间集合 intervals，即 [] | []
//        List<Integer> rangeOfSubGraphs = new ArrayList<Integer>();
//        for (int i = 0; i < intervals.size(); i += 2) {
//            int l = intervals.get(i), r = intervals.get(i + 1); // [l, r]
//            // 递归处理之
//            int subS = ++usedId; // 子图起点
//            int subT = this.convert(l, r, subS); // 子图终点
//            // 记录信息，把求解的结果放在 rangeOfSubGraphs 中
//            rangeOfSubGraphs.add(subS);
//            rangeOfSubGraphs.add(subT);
//            // 更新已分配 id
//            usedId = subT;
//        }
//        // 合并结果
//        int t = ++usedId; // 最后的 t
//        for (int i = 0; i < rangeOfSubGraphs.size(); i += 2) {
//            int startOfSubGraph = rangeOfSubGraphs.get(i), endOfSubGraph = rangeOfSubGraphs.get(i + 1);
//            this.nfa.addEdge(s, startOfSubGraph, ScannerFiniteAutomata.emptyTransit);
//            this.nfa.addEdge(endOfSubGraph, t, ScannerFiniteAutomata.emptyTransit);
//        }
//        return t; // return
//    }
//
//    /**
//     * 处理 re[l, r]，子图节点编号范围是 [s, t]
//     *
//     * @param l 区间左端点
//     * @param r 区间右端点
//     * @param s 初始编号，
//     * @return 结束编号 t，
//     */
//    private int convert(int l, int r, int s) {
//        // 边界情况考虑
//        try {
//            if (findMatchedRightIndex(l) == r) // 如果 l, r 处是匹配的括号
//                return convert(l + 1, r - 1, s);
//        } catch (Exception e) {
//        }
//        // 现在 [l, r] 不是一个 () 子区间
//        List<Integer> divideByUnion = this.divideByUnion(l, r);
//        if (divideByUnion.size() > 2) // 如果有多个 | 区间
//            return convertByUnion(s, divideByUnion);
//
//        // 现在 [l, r] 没有多个 | 区间，我们需要处理连接、闭包、括号子串
//        int usedId = s; // 当前编号 usedId，即已使用的最大编号，我们使用 ++usedId 进行分配
//        for (int i = l; i <= r; ++i) { // 用 i 遍历 [l, r]
//            // 假设当前生成的子图的开始-结束编号是 subS, subT
//            Integer subS = null, subT = null;
//            if (this.re.get(i) == StandardRE.LEFT_BRACKET) { // 如果位置 i 是 () 区间，
//                int subL = i; // 左括号，当前位置
//                int subR = this.findMatchedRightIndex(i); // 右括号
//                subS = usedId + 1;
//                subT = this.convert(subL, subR, subS); // 递归处理
//                this.nfa.addEdge(usedId, subS, ScannerFiniteAutomata.emptyTransit); // <生成前, 生成后, empty_trans>
//                i = subR; // 记得移动 i
//            } else if (this.re.get(i) == StandardRE.EMPTY_STR) { // 如果 i 的位置是空串转移
//                subS = usedId;
//                subT = subS + 1; // 构造获得 subS, subT
//                this.nfa.addEdge(subS, subT, ScannerFiniteAutomata.emptyTransit);
//            } else if (transitions.contains((int) this.re.get(i))) { // 如果 i 的位置是字母，
//                subS = usedId;
//                subT = subS + 1; // 构造获得 subS, subT
//                this.nfa.addEdge(subS, subT, this.re.get(i));
//            } else {
//                throw new IllegalArgumentException("转移表中不存在该符号");
//            }
//
//            // 如果下一处是闭包运算
//            if (i + 1 <= r && this.re.get(i + 1) == StandardRE.CLOSURE) {
//                this.nfa.addEdge(subS, subT, ScannerFiniteAutomata.emptyTransit); // 空
//                this.nfa.addEdge(subT, subS, ScannerFiniteAutomata.emptyTransit); // 回
//                ++i; // 向后移动一步
//            }
//            usedId = subT; // 记得更新 now_id
//        }
//        return usedId; // 返回结束编号
//
//    }
//
//    /**
//     * 将指定的正则表达式转换成 NFA，我们认为你的正则表达式有足够多的括号
//     *
//     * @param re          指定的正则表达式
//     * @param startId     自动机开始编号
//     * @param acceptId    接受值
//     * @return 转换后的 NFA
//     */
//    public ScannerFiniteAutomata convert(final String re, int startId, int acceptId) {
//        ExREToStREConverter reConverter = new ExREToStREConverter();
//        this.re = reConverter.convert(re);
//        this.transitions = reConverter.getTransitions();
//        int t = convert(0, this.re.size() - 1, startId + 1);
////		System.out.println(FiniteAutomata.emptyTransit);
//        this.nfa.addEdge(startId, startId + 1, ScannerFiniteAutomata.emptyTransit);
//        this.nfa.registerAcceptableNode(t, acceptId);
//        this.nfa.setStartId(startId);
//        return this.nfa;
//    }
//
//    /**
//     * 返回转移集合
//     * @return 返回转移集合
//     */
//    public Set<Integer> getTransitions() {
//        return this.transitions;
//    }
//}
